package main.Q701_800;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

public class Q761_770 {
    public static void main(String[] args) {
        System.out.println("Question761：");
        System.out.println("Question762：二进制表示中质数个计算置位");
        System.out.println("Question763：划分字母区间");
        System.out.println("Question764：");
        System.out.println("Question765：");
        System.out.println("Question766：托普利茨矩阵");
        System.out.println("Question767：重构字符串");
        System.out.println("Question768：");
        System.out.println("Question769：");
        System.out.println("Question770：");
    }
}

class Question762 {
    public int countPrimeSetBits(int left, int right) {
        int result = 0;
        for (int x = left; x <= right; ++x) {
            if (((1 << Integer.bitCount(x)) & 665772) != 0) {
                ++result;
            }
        }
        return result;
    }
}

class Question763 {
    public List<Integer> partitionLabels(String s) {
        List<Integer> list = new ArrayList<>();
        int[][] rang = new int[26][2];//每个字母起始和结束坐标
        char[] str = s.toCharArray();
        for (int i = 0; i < str.length; i++) {//记录每个字母范围
            int[] curRange = rang[str[i] - 'a'];
            if (curRange[0] == 0 && str[i] != str[0]) {//字母首次出现位置
                curRange[0] = i;
                curRange[1] = i;
            } else curRange[1] = i;//字母最后出现位置
        }
        System.out.println();
        Arrays.sort(rang, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                if (o1[0] != o2[0]) return o1[0] - o2[0];
                else return o2[1] - o1[1];
            }
        });
        int start = rang[0][0], end = rang[0][1];
        for (int i = 1; i < rang.length; i++) {
            int[] curRange = rang[i];
            if (curRange[1] < end) continue;//在当前范围内
            else if (curRange[0] < end && curRange[1] > end) {//部分重叠
                end = curRange[1];//扩展边界
            } else if (curRange[0] > end) {//无重叠
                list.add(end - start + 1);//重新划分
                start = curRange[0];
                end = curRange[1];
            }
        }
        list.add(end - start + 1);
        return list;
    }
}

class Question766 {
    public boolean process(int row, int col, int[][] matrix) {
        int value = matrix[row][col];
        while (row < matrix.length && col < matrix[0].length) {
            if (value != matrix[row][col]) return false;
            row++;
            col++;
        }
        return true;
    }

    public boolean isToeplitzMatrix(int[][] matrix) {
        for (int i = 0; i < matrix.length; i++) {//左列
            if (!process(i, 0, matrix)) {
                return false;
            }
        }
        for (int i = 0; i < matrix[0].length; i++) {//上行
            if (!process(0, i, matrix)) {
                return false;
            }
        }
        return true;
    }
}

class Question767 {
    public String reorganizeString(String s) {
        if (s.length() < 2) {
            return s;
        }
        int[] counts = new int[26];
        int maxCount = 0;
        int length = s.length();
        for (int i = 0; i < length; i++) {
            char c = s.charAt(i);
            counts[c - 'a']++;
            maxCount = Math.max(maxCount, counts[c - 'a']);
        }
        if (maxCount > (length + 1) / 2) {
            return "";
        }
        char[] reorganizeArray = new char[length];
        int evenIndex = 0, oddIndex = 1;
        int halfLength = length / 2;
        for (int i = 0; i < 26; i++) {
            char c = (char) ('a' + i);
            while (counts[i] > 0 && counts[i] <= halfLength && oddIndex < length) {
                reorganizeArray[oddIndex] = c;
                counts[i]--;
                oddIndex += 2;
            }
            while (counts[i] > 0) {
                reorganizeArray[evenIndex] = c;
                counts[i]--;
                evenIndex += 2;
            }
        }
        return new String(reorganizeArray);
    }
}